package uk.org.landeg.euler.problems;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;
import uk.org.landeg.euler.problems.lib.PrimeLib;

public class Problem037 extends AbstractProblem{
	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem037());
		launcher.solve();		
	}

	public static int truncateRight (int n) {
		return n/10;
	}
	
	public static int truncateLeft (int n) {
		if (n < 10) {
			return 0;
		}
		int test = 10;
		while (test < n) {
			test *= 10;
		}
		test /= 10;
		n -= test * (n /test);
		return n;
	}
	
	public static long truncateLeft (long n) {
		if (n < 10) {
			return 0;
		}
		int test = 10;
		while (test < n) {
			test *= 10;
		}
		test /= 10;
		n -= test * (n /test);
		return n;
	}
	
	static final int[] primeDigits = {1,3,5,7,9};
	Set<Integer> primes;
	Set<Integer> candidates;
	
	private void appendDigit (int n) {
		if (n > 1000000) {
			return;
		}
		int test ;
		boolean canAppend = false;
		for (int d : primeDigits) {
			test = n;
			test *= 10;
			test += d;
			if (primes.contains(test)) {
				appendDigit(test);
				canAppend = true;
			}
		}
		if (!canAppend && n > 10) {
			candidates.add(n);
		}
	}
	
	
	@Override
	public Object solve() {
		ArrayList<Integer> result = new ArrayList<Integer>();
		int testVal = 10;
		int truncLeft, truncRight;
		int total = 0;
		primes = PrimeLib.seqPrimes(1000000);
		boolean isCandidate;
		Iterator<Integer> it = primes.iterator();
		while (result.size() < 110 && it.hasNext()) {
			testVal = it.next();
			isCandidate = true;
			truncLeft = truncRight = testVal;
			while (truncLeft > 10 && truncRight > 10) {
				truncLeft = truncateLeft(truncLeft);
				truncRight = truncateRight(truncRight);
				if (!primes.contains(truncLeft) || !primes.contains(truncRight)) {
					isCandidate = false;
					break;
				}
			}
			if (isCandidate && testVal > 10) {
				result.add(testVal);
				total += testVal;
			}
		}
		System.out.println(total);
		return result;
	}
	
//	@Override
	public Object solveX() {
		Set<Integer> result = new HashSet<Integer>();
		candidates = new TreeSet<Integer>();
		primes = PrimeLib.seqPrimes(1000000);
		System.out.println("Finished Creating primes lookup " + primes.size());
		
		notes.add("Generate a list of candidate values by appending digits to known primes");
		notes.add("While the result is prime, continue adding digits until no more primes can be formed in this way");
		notes.add("At this point, add maximum length prime to a list of candidate values");
		notes.add("This represents all primes that can be trucated from the right.");
		appendDigit(0);
		System.out.println(candidates);
		notes.add("Now elimate candidate values that are not trunatable from left...");
		int t; boolean istrunc;
		
		int n;
		for (Integer check : candidates) {
			n = check;
			notes.add("Checking " +n );		
			istrunc = true;
			t = 1;
			while (n > 10) {
				while (t < n) t *= 10;
				t/=10;
				n -= t * (n/t);
				if (n > 1 && !primes.contains(n)) {
					notes.add("Truncated to "  + n + " == not a prime");
					istrunc = false;
					break;
				}
			}
			if (istrunc) {
				result.add(check);
			}
		}
		long total = 0;
		for (Integer i : result) {
			total += i;
		}
		return result;
	}

	@Override
	public String getDescription() {
		return "Find the sum of all 11 truncatable primes";
	}

	@Override
	public Integer getProblemNumber() {
		return 37;
	}
}
